package com.darrenchan.leetcode;

import java.util.*;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-30 14:29
 */
class Node2 {
    public int val;
    public List<Node2> neighbors;

    public Node2() {
    }

    public Node2(int _val, List<Node2> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

public class Q133 {
    public Node2 cloneGraph(Node2 node) {
        Node2 root = node;
        if (root == null) {
            return null;
        }
        Set<Node2> nodes = getNodes(node);
        Map<Node2, Node2> map = new HashMap<>();
        //先创建新的节点
        for (Node2 n : nodes) {
            Node2 newNode = new Node2();
            newNode.val = n.val;
            newNode.neighbors = new ArrayList<>();
            map.put(n, newNode);
        }
        //再关联所有的边
        for (Node2 n : map.keySet()) {
            Node2 newNode = map.get(n);

            for (Node2 neighbor : n.neighbors) {
                newNode.neighbors.add(map.get(neighbor));
            }
        }
        return map.get(root);
    }

    private Set<Node2> getNodes(Node2 node) {
        Set<Node2> res = new HashSet<>();
        Queue<Node2> queue = new LinkedList<>();
        queue.add(node);
        res.add(node);
        while (!queue.isEmpty()) {
            node = queue.poll();
            for (Node2 neighbor : node.neighbors) {
                if (!res.contains(neighbor)) {
                    queue.add(neighbor);
                    res.add(neighbor);
                }
            }
        }

        return res;
    }
}
